package DP.子序列;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    先按长排序
    宽dp：dp[i]=包含i的最长增序长度
         回头找max 长宽都严格小于 (不能等于

    (‘用flag记找没找到-太乱’不如用：初始=1, Math.max(dp[i]覆盖，代码简便
 */
public class 俄罗斯套娃信封问题354 {
    @Test
    public void test() {
        int[][] p = {{5,4},{6,4},{6,7},{2,3}};
        System.out.println(maxEnvelopes(p));
    }

    public int maxEnvelopes(int[][] g) {
        //先长排序
        Arrays.sort(g, (a,b)->b[0]-a[0]);
        //再宽dp
        int[] k = new int[g.length];
        for (int i = 0; i < g.length; i++) {
            k[i] = g[i][1];
        }
        //dp[i]=包含i的最长增序长度
        int[] dp = new int[k.length];
        dp[0]=1;
        for (int i = 0; i < dp.length; i++) {
            //初始化为1，防止没找到赋值为0
            dp[i]=1;
            for (int j = 0; j < i; j++) {
                //max从 宽小于&长小于 中找，[关键字：“中”]
                if(k[i]<k[j] && g[i][0]<g[j][0]){
                    //dp[i]巧妙：用覆盖实现记录最大值
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        //遍历找最大
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }
}
